/*
 * @lc app=leetcode.cn id=931 lang=java
 *
 * [931] 下降路径最小和
 */

// @lc code=start
import java.util.Arrays;
class Solution {
    private int[][] matrix, memo;
    public int minFallingPathSum(int[][] matrix) {
        this.matrix = matrix;

        int n = matrix.length;
        memo = new int[n][n];

        for(int i = 0; i < n; i++) {
            Arrays.fill(memo[i], Integer.MIN_VALUE);
        }

        int res = Integer.MAX_VALUE;

        for(int j = 0; j < n; j++) {
            res = Math.min(res, dfs(n - 1, j));
        }

        return res;


    }

    private int dfs(int n, int j) {
        if(j < 0 || j >= matrix.length) {
            return Integer.MAX_VALUE;
        }

        if(n == 0) {
            return matrix[0][j];
        }

        if(memo[n][j] != Integer.MIN_VALUE) {
            return memo[n][j];
        }

        return memo[n][j] = matrix[n][j] + Math.min(dfs(n - 1, j + 1), Math.min(dfs(n - 1, j), dfs(n - 1, j - 1)));
    }
}
// @lc code=end

